#include<stdio.h>
#include<stdlib.h>

typedef struct ListNode ListNode;
struct ListNode
{
    int val;
    ListNode* next;
};

// merge l2 to l1, and return the new head of l1
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
{
    ListNode *i = l1,*j = l2, *k = NULL;
    ListNode *nh = NULL;

    while(i && j)
    {
        if(j->val < i->val)
        {
            if(!k)
            {
                nh = k = j;
                j = j->next;
                nh->next = l1;
            }
            else
            {
                ListNode* tmp = j;
                j = j->next;
                tmp->next = k->next; k->next = tmp;
                k = k->next;
            }
        }
        else
        {
            if(!k)nh = k = i;
            else k = k->next;
            i = i->next; 
        }
    }
    while(i)
    {
        if(!k) nh = k = i;
        else k = k->next;
        i = i->next;
    }
    while(j)
    {
        if(!k)
        {
            nh = k = j;
            j = j->next;
            nh->next = l1;
        }
        else
        {
            ListNode* tmp = j;
            j = j->next;
            tmp->next = k->next; k->next = tmp;
            k = k->next;
        }
    }
    return nh;
}

int main(int argc, char const *argv[])
{
    
    return 0;
}
